home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / textbooks / reade / life.sml < prev    next >
Encoding:
Text File  |  1995-12-30  |  3.6 KB  |  70 lines  |  [TEXT/R*ch]
  1.  
  2. (*************************************************************************************
  3.  * A structure containing definitions for the game of life                           *
  4.  * C.Reade 5/1/87 (Modified Oct 1987)                                                *
  5.  *************************************************************************************
  6.  * type generation
  7.  * val mkgen         : (int * int) list -> generation
  8.  * val alive         : generation -> (int * int) list
  9.  * val mk_nextgen_fn : ((int * int) -> (int * int) list) -> (generation -> generation)
  10.  *------------------------------------------------------------------------------------
  11.  * generation is an abstract type with operations mkgen and alive and mk_nextgen_fn.
  12.  * mkgen produces a generation from an arbitrary list of coordinates (integer pairs)
  13.  *   for live squares.
  14.  * alive produces the list of coordinates of live squares of a generation
  15.  *   in lexical order (with no repetitions).
  16.  * mk_nextgen_fn can be used to produce a nextgeneration function of type
  17.  *   generation -> generation. It should be supplied with an argument function
  18.  * which calculates the neighbours of a coordinate. For example, if you first define
  19.  *                            neighbours:(int*int)->(int*int)list 
  20.  * Then you can define        val nextgen = mk_nextgen_fn (neighbours)
  21.  * This allows you to experiment with different neighbour functions (usually 8 neigh-
  22.  * bours possibly modified with wraparound or cutoff at some upper and lower limits).
  23.  ************************************************************************************)
  24. structure Life =
  25. struct
  26.    local (*********************** AUXILIARY DEFINITIONS *****************************)
  27.     val filter  = Chrisprelude.filter;
  28.     val length = Chrisprelude.length;
  29.     val member = Chrisprelude.member;
  30.     val revonto = Chrisprelude.revonto;
  31.     fun lexordset [] = []
  32.       | lexordset (a::x) = lexordset(filter (lexless a) x) @ [a] @
  33.                            lexordset(filter (lexgreater a) x)
  34.     and lexless (a1:int,b1:int) (a2,b2) = a2<a1 orelse (a2=a1 andalso b2<b1)
  35.     and lexgreater pr1 pr2 = lexless pr2 pr1;
  36.     fun collect f list 
  37.             = let fun accumf sofar [] = sofar
  38.                     | accumf sofar (a::x) = accumf (revonto sofar (f a)) x
  39.               in accumf [] list end;
  40.     fun occurs3 x   (* finds coords which occur exactly 3 times in coordlist x *)
  41.         = let fun f xover x3 x2 x1 [] = diff x3 xover
  42.                 | f xover x3 x2 x1 (a::x)
  43.                    = if member xover a then f xover x3 x2 x1 x else
  44.                      if member x3 a then f (a::xover) x3 x2 x1 x else
  45.                      if member x2 a then f xover (a::x3) x2 x1 x else
  46.                      if member x1 a then f xover x3 (a::x2) x1 x else
  47.                                          f xover x3 x2 (a::x1) x
  48.               and diff x y = filter (not o member y) x
  49.           in f [] [] [] [] x end
  50.   in (*********************** MAIN DEFINITIONS FOLLOW *******************************)
  51.  
  52. abstype generation = GEN of (int*int)list
  53.    with
  54.      fun alive (GEN livecoords) = livecoords
  55.      and mkgen coordlist = GEN(lexordset coordlist)
  56.      and mk_nextgen_fn neighbours gen
  57.           = let val living = alive gen
  58.                 val isalive = member living
  59.                 val liveneighbours = length o filter isalive o neighbours
  60.                 fun twoorthree n = n=2 orelse n=3
  61.                 val survivors = filter (twoorthree o liveneighbours) living
  62.                 val newnbrlist = collect (filter (not o isalive) o neighbours) living
  63.                 val newborn = occurs3 newnbrlist
  64.             in mkgen(survivors @ newborn) end
  65.    end
  66.  
  67. end (* of local *)
  68. end (* of Life *);
  69.  
  70.